package Class028_基数排序;

import Class021.Merge;
import Utils.ArrayUtils;

import java.util.Arrays;

//基数排序: 不基于比较的排序 但是对对象特征有要求，不通用
//计数排序: 对于给定范围的数组，比如告诉你范围是0~60，那么可以进行一次词频统计，然后填进去
//        但是范围大了就不行了
//一般而言，计数排序要求样本为整数，范围比较窄
//基数排序要求样本是10进制的非负整数
//基数排序也称为桶排序，看一下最大数有几位
//按照个位到最高位，依次进对应的桶进行排序，先进先出吗，也就是按照位数排序
//桶的编号就是0~9
//很明显，这个是一个稳定的排序，相对的位置会被保留
public class RadixSort {
    public static int BASE = 10;
    public static int AMOUNT = 10000;
    public static int MAX = 6000;
    public static int[] cnt = new int[BASE];
    public static void main(String[] args) {
        test();
    }

    public static void radixSort(int[] arr) {
        int min = convertToPositive(arr);
        myRadixSort(arr, arr.length, getBits(arr));
        if(min < 0)
            rollBackToOriginal(arr, min);
    }

    //如果数组中有负数，也可以排序。找到最小值，然后统一加上
    //该方法完成这个任务，返回是否进行了这种操作
    public static int convertToPositive(int[] arr) {
        int min = Integer.MAX_VALUE;
        for(int i: arr) {
            min = Math.min(min, i);
        }
        if(min < 0) {
            for(int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
        }
        return min;
    }

    //如果上面的方法返回值 < 0，需要调用此方法转回去
    public static void rollBackToOriginal(int[] arr, int min) {
        for(int i = 0; i < arr.length; i++) {
            arr[i] += min;
        }
    }

    public static int getBits(int[] arr) {
        int max = -1;
        int bits = 0;
        for(int i: arr) {
            max = Math.max(max, i);
        }
        while(max > 0) {
            bits++;
            max /= BASE;
        }
        return bits;
    }

    //n是arr的长度
    //bits是在当前进制下的最高位数
    //使用的技巧: 前缀分区
    //以个位数的数组为例。假设数组为[0,3,2,4,7]
    //使用某种统计的方式，可以分别得到：
    //<= 0: 1个
    //<= 2: 2个
    //<= 3: 3个
    //<= 4: 4个
    //<= 7: 5个
    //将数组从后往前遍历，遇到7，发现<= 7的有5个，那么将其放在help数组的第4个位置，同时将<=7 的记录-1
    //但是，不要动其他位置的记录。
    //流程跑完，数组排好序，并且相对位置不变
    //最高位为n位，那么就跑n轮即可
    public static void myRadixSort(int[] arr, int N, int bits) {
        int[] help = new int[N];
        for(int offset = 1; bits > 0; bits--, offset *= BASE) {
            //cnt全部置0
            Arrays.fill(cnt, 0);
            //1. 遍历数组，统计当前位为0~9的有几个数字
            for(int i = 0; i < N; i++) {
                cnt[(arr[i] / offset) % BASE]++;
            }
            //2. 利用前缀和原理，可以得到 <= 0~9的分别有多少个，简单的累加就行
            for(int i = 1; i < BASE; i++) {
                cnt[i] = cnt[i] + cnt[i - 1];
            }
            //3. 从后往前遍历数组，为的是保证相对位置不变，填入help数组
            for(int i = N - 1; i >= 0; i--) {
                help[--cnt[(arr[i] / offset) % BASE]] = arr[i];
            }
            //4. help倒进arr
            for(int i = 0; i < N; i++) {
                arr[i] = help[i];
            }
        }
    }
    public static void test() {
        int time = 1000;
        int errTime = 0;
        System.out.println("Correctness Test:");
        for (int i = 0; i < time; i++) {
//            int[] base = ArrayUtils.generatePositiveArray(AMOUNT, MAX);
            int[] base = ArrayUtils.generateArray(AMOUNT, MAX);
            int[] right = Arrays.copyOf(base, base.length);
            int[] better = Arrays.copyOf(base, base.length);
            Merge.myMerge(right, false);
            radixSort(better);
            if (!ArrayUtils.judge(right, better)) {
                System.out.println(Arrays.toString(base));
                System.out.println("Should be:");
                System.out.println(Arrays.toString(right));
                System.out.println("Wrong answer:");
                System.out.println(Arrays.toString(better));
                errTime++;
            }
        }
        if (errTime == 0) {
            System.out.println("All clear.");
        } else {
            System.out.println("Errors:" + errTime + "/" + time);
            System.out.println("Accuracy:" + (time - errTime) * 1.0 / time);
            return;
        }

        System.out.println("Time test:");
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(AMOUNT, MAX);
//            int[] base = ArrayUtils.generatePositiveArray(AMOUNT, MAX);
            radixSort(base);
        }
        e = System.currentTimeMillis();
        System.out.println("Radix Sort:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(AMOUNT, MAX);
//            int[] base = ArrayUtils.generatePositiveArray(AMOUNT, MAX);
            Merge.myMerge(base, false);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Ite):" + (e - s) + "ms");
    }
}
